|
In computer science, software pipelining is a technique used to optimize loops, in a manner that parallels hardware pipelining. Software pipelining is a type of out-of-order execution, except that the reordering is done by a compiler (or in the case of hand written assembly code, by the programmer) instead of the processor. Some computer architectures have explicit support for software pipelining, notably Intel's IA-64 architecture. It is important to distinguish ''software pipelining'' which is a target code technique for overlapping loop iterations, from ''modulo scheduling'', the currently most effective known compiler technique for generating software pipelined loops. Software pipelining has been known to assembly language programmers of machines with instruction level parallelism since such architectures existed. Effective compiler generation of such code dates to the invention of modulo scheduling by Rau and Glaeser.〔B.R. Rau and C.D. Glaeser, "Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing", In ''Proceedings of the Fourteenth Annual Workshop on Microprogramming (MICRO-14),'' December 1981, pages 183-198〕 Lam showed that special hardware is unnecessary for effective modulo scheduling. Her technique, ''modulo renaming'' is widely used in practice.〔M. Lam, "Software pipelining: An effective scheduling technique for VLIW machines", In ''Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (PLDI 88)'', July 1988 pages 318-328. Also published as ACM SIGPLAN Notices 23(7).〕 Gao et al. formulated optimal software pipelining in integer linear programming, culminating in validation of advanced heuristics in an evaluation paper.〔J. Ruttenberg, G.R. Gao, A. Stoutchinin, and W. Lichtenstein, "Software pipelining showdown: optimal vs. heuristic methods in a production compiler", In ''Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation,'' June 1996, pages 1-11. Also published as ACM SIGPLAN Notices 31(5).〕 This paper has a good set of references on the topic. ==Example== Consider the following loop: for i = 1 to bignumber A(i) B(i) C(i) end In this example, let A(i), B(i), C(i) be instructions, each operating on data i, that are dependent on each other. In other words, A(i) must complete before B(i) can start. For example, A could load data from memory into a register, B could perform some arithmetic operation on the data, and C could store the data back into memory. However, let there be no dependence between operations for different values of i. In other words, A(2) can begin before A(1) finishes.Without software pipelining, the operations execute in the following sequence: A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ... Assume that each instruction takes 3 clock cycles to complete (ignore for the moment the cost of the looping control flow). Also assume (as is the case on most modern systems) that an instruction can be dispatched every cycle, as long as it has no dependencies on an instruction that is already executing. In the unpipelined case, each iteration thus takes 7 cycles to complete (3 + 3 + 1, because A(i+1) does not have to wait for C(i))Now consider the following sequence of instructions (with software pipelining): A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ... It can be easily verified that an instruction can be dispatched each cycle, which means that the same 3 iterations can be executed in a total of 9 cycles, giving an average of 3 cycles per iteration. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「software pipelining」の詳細全文を読む スポンサード リンク
|